/**
 * //给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 * //
 * // 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
 * //
 * // 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * //
 * //输入: nums = [1,2,3,4]
 * //输出: [24,12,8,6]
 * //
 * //
 * // 示例 2:
 * //
 * //
 * //输入: nums = [-1,1,0,-3,3]
 * //输出: [0,0,9,0,0]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 2 <= nums.length <= 10⁵
 * // -30 <= nums[i] <= 30
 * // 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
 * //
 * //
 * //
 * //
 * // 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
 * //
 * // Related Topics 数组 前缀和 👍 1268 👎 0
 */

package com.xixi.basicAlgroithms.dualPointer;

public class ID00238ProductOfArrayExceptSelf {
    public static void main(String[] args) {
        Solution solution = new ID00238ProductOfArrayExceptSelf().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] productExceptSelf(int[] nums) {

            int n = nums.length;
            int[] answer = new int[n];

            //不包含该数字的前缀和，首位为1
            answer[0] = 1;
            int i = 1;
            int fProduct = 1;
            while (i < n) {
                fProduct *= nums[i - 1];
                answer[i] = fProduct;
                i++;
            }


            //不包含该数字的后缀和，末位为1
            i = n - 2;
            int rProduct = 1; //返回乘积
            while (i >= 0) {
                rProduct *= nums[i + 1];
                answer[i] *= rProduct;
                i--;
            }


            return answer;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}